package com.java_foundation.arithmetic;

public class ShellSort {
    /**
     * 希尔排序
     *
     * 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
     * 2. 按增量序列个数k，对序列进行k 趟排序；
     * 3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
     *    仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     * @param nums  待排序数组
     */
    public void shellSort(int[] nums){
        int gap = 1,i,j,len = nums.length;
        int temp;
        while(gap < len / 3){
            gap = gap * 3 + 1;
        }
        for(; gap > 0;gap /= 3){
            for(i = gap;i < len;i++){
                temp = nums[i];
                for(j = i - gap; j >= 0 && nums[j] > temp; j-=gap){
                    nums[j+gap] = nums[j];
                }
                nums[j+gap] = temp;
            }
        }

    }
}
